home *** CD-ROM | disk | FTP | other *** search
/ MacHack 1998 / MacHack 1998.toast / Programming Contest / MacHack Contest.sit / MacHack Contest / Problems Folder / Problem 07 - Graph / Solution.cp < prev    next >
MacBinary  |  1998-06-18  |  2.5 KB  |  [TEXT/CWIE]
open in: MacOS 8.1     |     Win98     |     DOS

browse contents    |     view JSON data     |     view as text


This file was processed as: MacBinary (archive/macBinary).

ConfidenceProgramDetectionMatch TypeSupport
10% dexvert MacBinary (archive/macBinary) fallback Supported
1% dexvert MS-DOS Code Page Info (other/dosCodePage) ext Unsupported
1% dexvert Text File (text/txt) fallback Supported
100% file MacBinary II, Thu Jun 18 12:48:48 1998, modified Thu Jun 18 12:48:48 1998, creator 'CWIE', type ASCII, 1851 bytes "Solution.cp" , at 0x7bb 410 bytes resource default (weak)
99% file data default
74% TrID Macintosh plain text (MacBinary) default
25% TrID MacBinary 2 default (weak)
100% siegfried fmt/1762 MacBinary (II) default
100% lsar MacBinary default


id metadata
keyvalue
macFileType[TEXT]
macFileCreator[CWIE]


hex view
+--------+-------------------------+-------------------------+--------+--------+
|00000000| 00 0b 53 6f 6c 75 74 69 | 6f 6e 2e 63 70 00 00 00 |..Soluti|on.cp...|
|00000010| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000020| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000030| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000040| 00 54 45 58 54 43 57 49 | 45 00 00 00 00 00 00 00 |.TEXTCWI|E.......|
|00000050| 00 00 00 00 00 07 3b 00 | 00 01 9a b1 ae f5 70 b1 |......;.|......p.|
|00000060| ae f5 70 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |..p.....|........|
|00000070| 00 00 00 00 00 00 00 00 | 00 00 81 81 4d b6 00 00 |........|....M...|
|00000080| 2f 2a 0d 50 72 6f 62 6c | 65 6d 20 30 37 20 2d 20 |/*.Probl|em 07 - |
|00000090| 47 72 61 70 68 0d 0d 70 | 72 6f 63 65 64 75 72 65 |Graph..p|rocedure|
|000000a0| 20 47 72 61 70 68 49 6e | 69 74 28 20 76 61 72 20 | GraphIn|it( var |
|000000b0| 67 72 61 70 68 3a 20 48 | 61 6e 64 6c 65 3b 20 76 |graph: H|andle; v|
|000000c0| 65 72 72 74 69 63 69 65 | 73 3a 20 55 49 6e 74 33 |errticie|s: UInt3|
|000000d0| 32 20 29 3b 0d 70 72 6f | 63 65 64 75 72 65 20 47 |2 );.pro|cedure G|
|000000e0| 72 61 70 68 41 64 64 44 | 69 72 65 63 74 65 64 45 |raphAddD|irectedE|
|000000f0| 64 67 65 28 20 67 72 61 | 70 68 3a 20 48 61 6e 64 |dge( gra|ph: Hand|
|00000100| 6c 65 3b 20 76 65 72 74 | 65 78 31 2c 20 76 65 72 |le; vert|ex1, ver|
|00000110| 74 65 78 32 3a 20 55 49 | 6e 74 33 32 20 29 3b 0d |tex2: UI|nt32 );.|
|00000120| 70 72 6f 63 65 64 75 72 | 65 20 47 72 61 70 68 46 |procedur|e GraphF|
|00000130| 69 6e 64 52 6f 75 74 65 | 28 20 67 72 61 70 68 3a |indRoute|( graph:|
|00000140| 20 48 61 6e 64 6c 65 3b | 20 76 65 72 74 65 78 31 | Handle;| vertex1|
|00000150| 2c 20 76 65 72 74 65 78 | 32 3a 20 55 49 6e 74 33 |, vertex|2: UInt3|
|00000160| 32 3b 20 76 61 72 0d 76 | 65 72 74 69 63 69 65 73 |2; var.v|erticies|
|00000170| 3a 20 48 61 6e 64 6c 65 | 20 29 3b 0d 0d 59 6f 75 |: Handle| );..You|
|00000180| 72 20 74 61 73 6b 20 69 | 73 20 74 6f 20 77 72 69 |r task i|s to wri|
|00000190| 74 65 20 61 20 73 65 74 | 20 6f 66 20 72 6f 75 74 |te a set| of rout|
|000001a0| 69 6e 65 73 20 74 6f 20 | 63 72 65 61 74 65 20 61 |ines to |create a|
|000001b0| 6e 64 20 74 72 61 76 65 | 72 73 65 20 61 20 64 69 |nd trave|rse a di|
|000001c0| 72 65 63 74 65 64 0d 67 | 72 61 70 68 2e 0d 0d 47 |rected.g|raph...G|
|000001d0| 72 61 70 68 49 6e 69 74 | 20 63 72 65 61 74 65 73 |raphInit| creates|
|000001e0| 20 61 20 6e 65 77 2c 20 | 65 6d 70 74 79 20 64 69 | a new, |empty di|
|000001f0| 72 65 63 74 65 64 20 67 | 72 61 70 68 20 72 65 61 |rected g|raph rea|
|00000200| 64 79 20 74 6f 20 61 63 | 63 65 70 74 20 64 69 72 |dy to ac|cept dir|
|00000210| 65 63 74 65 64 20 65 64 | 67 65 73 0d 77 69 74 68 |ected ed|ges.with|
|00000220| 20 76 65 72 72 74 69 63 | 69 65 73 20 76 65 72 74 | verrtic|ies vert|
|00000230| 69 63 69 65 73 2e 20 20 | 0d 0d 47 72 61 70 68 41 |icies.  |..GraphA|
|00000240| 64 64 44 69 72 65 63 74 | 65 64 45 64 67 65 20 61 |ddDirect|edEdge a|
|00000250| 64 64 73 20 61 20 64 69 | 72 65 63 74 65 64 20 65 |dds a di|rected e|
|00000260| 64 67 65 20 66 72 6f 6d | 20 76 65 72 74 65 78 31 |dge from| vertex1|
|00000270| 20 74 6f 20 76 65 72 74 | 65 78 32 0d 0d 47 72 61 | to vert|ex2..Gra|
|00000280| 70 68 46 69 6e 64 52 6f | 75 74 65 20 66 69 6e 64 |phFindRo|ute find|
|00000290| 20 61 20 72 6f 75 74 65 | 20 66 72 6f 6d 20 76 65 | a route| from ve|
|000002a0| 72 74 65 78 31 20 74 6f | 20 76 65 72 74 65 78 32 |rtex1 to| vertex2|
|000002b0| 2e 20 20 49 66 20 73 75 | 63 68 20 61 20 72 6f 75 |.  If su|ch a rou|
|000002c0| 74 65 20 65 78 69 73 74 | 73 2c 0d 74 68 65 6e 20 |te exist|s,.then |
|000002d0| 76 65 72 74 69 63 69 65 | 73 20 69 73 20 72 65 74 |verticie|s is ret|
|000002e0| 75 72 6e 73 20 61 73 20 | 61 20 72 65 61 6c 20 4d |urns as |a real M|
|000002f0| 61 63 20 68 61 6e 64 6c | 65 20 74 6f 20 61 6e 20 |ac handl|e to an |
|00000300| 61 72 72 61 79 20 6f 66 | 20 55 49 6e 74 33 32 73 |array of| UInt32s|
|00000310| 2c 20 74 68 65 0d 66 69 | 72 73 74 20 69 73 20 76 |, the.fi|rst is v|
|00000320| 65 72 74 65 78 31 2c 20 | 74 68 65 20 6c 61 73 74 |ertex1, |the last|
|00000330| 20 69 73 20 76 65 72 74 | 65 78 32 2e 20 20 45 61 | is vert|ex2.  Ea|
|00000340| 63 68 20 73 75 63 63 65 | 73 73 69 76 65 20 76 65 |ch succe|ssive ve|
|00000350| 72 74 65 78 20 6d 75 73 | 74 20 68 61 76 65 0d 70 |rtex mus|t have.p|
|00000360| 72 65 76 69 6f 75 73 6c | 79 20 68 61 64 20 61 6e |reviousl|y had an|
|00000370| 20 65 64 67 65 20 61 64 | 64 65 64 20 77 69 74 68 | edge ad|ded with|
|00000380| 20 47 72 61 70 68 41 64 | 64 44 69 72 65 63 74 65 | GraphAd|dDirecte|
|00000390| 64 45 64 67 65 2e 20 20 | 49 66 20 6e 6f 20 72 6f |dEdge.  |If no ro|
|000003a0| 75 74 65 20 65 78 69 73 | 74 73 2c 0d 72 65 74 75 |ute exis|ts,.retu|
|000003b0| 72 6e 20 6e 69 6c 20 66 | 6f 72 20 76 65 72 74 69 |rn nil f|or verti|
|000003c0| 63 69 65 73 2e 20 20 4e | 6f 20 76 65 72 74 65 78 |cies.  N|o vertex|
|000003d0| 20 73 68 6f 75 6c 64 20 | 61 70 70 65 61 72 20 6d | should |appear m|
|000003e0| 6f 72 65 20 74 68 61 6e | 20 6f 6e 63 65 20 69 6e |ore than| once in|
|000003f0| 20 74 68 65 0d 76 65 72 | 74 69 63 69 65 73 20 68 | the.ver|ticies h|
|00000400| 61 6e 64 6c 65 2c 20 65 | 78 63 65 70 74 20 66 6f |andle, e|xcept fo|
|00000410| 72 20 74 68 65 20 63 61 | 73 65 20 77 68 65 72 65 |r the ca|se where|
|00000420| 20 76 65 72 74 65 78 31 | 20 69 73 20 74 68 65 20 | vertex1| is the |
|00000430| 73 61 6d 65 20 61 73 20 | 76 65 72 74 65 78 32 2c |same as |vertex2,|
|00000440| 20 69 6e 0d 77 68 69 63 | 68 20 63 61 73 65 20 79 | in.whic|h case y|
|00000450| 6f 75 20 6d 75 73 74 20 | 66 69 6e 64 20 61 20 63 |ou must |find a c|
|00000460| 69 72 63 75 6c 61 72 20 | 72 6f 75 74 65 20 66 72 |ircular |route fr|
|00000470| 6f 6d 20 76 65 72 74 65 | 78 31 20 62 61 63 6b 20 |om verte|x1 back |
|00000480| 74 6f 20 69 74 73 65 6c | 66 20 61 6e 64 20 73 6f |to itsel|f and so|
|00000490| 0d 76 65 72 74 65 78 31 | 20 77 69 6c 6c 20 61 70 |.vertex1| will ap|
|000004a0| 70 65 61 72 20 65 78 61 | 63 74 6c 79 20 74 77 69 |pear exa|ctly twi|
|000004b0| 63 65 2c 20 6f 6e 63 65 | 20 61 74 20 74 68 65 20 |ce, once| at the |
|000004c0| 73 74 61 72 74 20 61 6e | 64 20 6f 6e 63 65 20 61 |start an|d once a|
|000004d0| 74 20 74 68 65 20 65 6e | 64 20 6f 66 20 74 68 65 |t the en|d of the|
|000004e0| 0d 76 65 72 74 69 63 69 | 65 73 20 68 61 6e 64 6c |.vertici|es handl|
|000004f0| 65 2e 0d 0d 41 6c 6c 20 | 74 68 65 20 67 72 61 70 |e...All |the grap|
|00000500| 68 20 69 6e 66 6f 72 6d | 61 74 69 6f 6e 20 6d 75 |h inform|ation mu|
|00000510| 73 74 20 62 65 20 73 74 | 6f 72 65 64 20 69 6e 20 |st be st|ored in |
|00000520| 74 68 65 20 72 65 61 6c | 20 4d 61 63 20 6d 65 6d |the real| Mac mem|
|00000530| 6f 72 79 20 6d 61 6e 61 | 67 65 72 20 68 61 6e 64 |ory mana|ger hand|
|00000540| 6c 65 0d 2d 20 69 74 20 | 77 69 6c 6c 20 62 65 20 |le.- it |will be |
|00000550| 64 69 73 70 6f 73 65 64 | 20 77 69 74 68 20 44 69 |disposed| with Di|
|00000560| 73 70 6f 73 65 48 61 6e | 64 6c 65 20 61 6e 64 20 |sposeHan|dle and |
|00000570| 74 68 61 74 20 6d 75 73 | 74 20 72 65 6c 65 61 73 |that mus|t releas|
|00000580| 65 20 61 6c 6c 20 6d 65 | 6d 6f 72 79 2c 20 73 6f |e all me|mory, so|
|00000590| 0d 64 6f 6e 74 20 73 74 | 6f 72 65 20 61 6e 79 20 |.dont st|ore any |
|000005a0| 65 78 74 72 61 20 69 6e | 66 6f 72 6d 61 74 69 6f |extra in|formatio|
|000005b0| 6e 20 6f 75 74 73 69 64 | 65 20 74 68 65 20 68 61 |n outsid|e the ha|
|000005c0| 6e 64 6c 65 2e 20 20 41 | 6c 73 6f 2c 20 79 6f 75 |ndle.  A|lso, you|
|000005d0| 20 6d 75 73 74 20 62 65 | 20 61 62 6c 65 20 74 6f | must be| able to|
|000005e0| 0d 64 65 61 6c 20 77 69 | 74 68 20 68 61 76 69 6e |.deal wi|th havin|
|000005f0| 67 20 6d 75 6c 74 69 70 | 6c 65 20 67 72 61 70 68 |g multip|le graph|
|00000600| 73 20 69 6e 73 74 61 6e | 74 69 61 74 65 64 20 73 |s instan|tiated s|
|00000610| 69 6d 75 6c 74 61 6e 65 | 6f 75 73 6c 79 2e 0d 2a |imultane|ously..*|
|00000620| 2f 0d 0d 23 69 6e 63 6c | 75 64 65 20 22 53 6f 6c |/..#incl|ude "Sol|
|00000630| 75 74 69 6f 6e 2e 68 22 | 0d 0d 2f 2f 20 46 69 6c |ution.h"|..// Fil|
|00000640| 6c 20 69 6e 20 79 6f 75 | 72 20 73 6f 6c 75 74 69 |l in you|r soluti|
|00000650| 6f 6e 20 61 6e 64 20 74 | 68 65 6e 20 73 75 62 6d |on and t|hen subm|
|00000660| 69 74 20 74 68 69 73 20 | 66 6f 6c 64 65 72 0d 0d |it this |folder..|
|00000670| 2f 2f 20 54 65 61 6d 20 | 4e 61 6d 65 3a 20 46 49 |// Team |Name: FI|
|00000680| 4c 4c 20 49 4e 20 59 4f | 55 52 20 54 45 41 4d 20 |LL IN YO|UR TEAM |
|00000690| 4e 41 4d 45 21 0d 0d 70 | 61 73 63 61 6c 20 76 6f |NAME!..p|ascal vo|
|000006a0| 69 64 20 47 72 61 70 68 | 49 6e 69 74 28 20 48 61 |id Graph|Init( Ha|
|000006b0| 6e 64 6c 65 20 2a 67 72 | 61 70 68 2c 20 55 49 6e |ndle *gr|aph, UIn|
|000006c0| 74 33 32 20 76 65 72 74 | 69 63 69 65 73 20 29 0d |t32 vert|icies ).|
|000006d0| 7b 0d 09 2a 67 72 61 70 | 68 20 3d 20 6e 69 6c 3b |{..*grap|h = nil;|
|000006e0| 0d 7d 0d 0d 70 61 73 63 | 61 6c 20 76 6f 69 64 20 |.}..pasc|al void |
|000006f0| 47 72 61 70 68 41 64 64 | 44 69 72 65 63 74 65 64 |GraphAdd|Directed|
|00000700| 45 64 67 65 28 20 48 61 | 6e 64 6c 65 20 67 72 61 |Edge( Ha|ndle gra|
|00000710| 70 68 2c 20 55 49 6e 74 | 33 32 20 76 65 72 74 65 |ph, UInt|32 verte|
|00000720| 78 31 2c 20 55 49 6e 74 | 33 32 20 76 65 72 74 65 |x1, UInt|32 verte|
|00000730| 78 32 20 29 0d 7b 0d 7d | 0d 0d 70 61 73 63 61 6c |x2 ).{.}|..pascal|
|00000740| 20 76 6f 69 64 20 47 72 | 61 70 68 46 69 6e 64 52 | void Gr|aphFindR|
|00000750| 6f 75 74 65 28 20 48 61 | 6e 64 6c 65 20 67 72 61 |oute( Ha|ndle gra|
|00000760| 70 68 2c 20 55 49 6e 74 | 33 32 20 76 65 72 74 65 |ph, UInt|32 verte|
|00000770| 78 31 2c 20 55 49 6e 74 | 33 32 20 76 65 72 74 65 |x1, UInt|32 verte|
|00000780| 78 32 2c 20 55 49 6e 74 | 33 32 41 72 72 61 79 48 |x2, UInt|32ArrayH|
|00000790| 61 6e 64 6c 65 20 2a 76 | 65 72 74 69 63 69 65 73 |andle *v|erticies|
|000007a0| 20 29 0d 7b 0d 09 2a 76 | 65 72 74 69 63 69 65 73 | ).{..*v|erticies|
|000007b0| 20 3d 20 6e 69 6c 3b 0d | 7d 0d 0d 00 00 00 00 00 | = nil;.|}.......|
|000007c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000007d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000007e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000007f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000800| 00 00 01 00 00 00 01 54 | 00 00 00 54 00 00 00 46 |.......T|...T...F|
|00000810| 2b 30 38 30 30 31 35 3a | 35 35 3a 33 32 20 31 39 |+080015:|55:32 19|
|00000820| 39 38 00 00 00 00 00 00 | 00 00 b1 78 6a 77 00 00 |98......|...xjw..|
|00000830| 0b 53 6f 6c 75 74 69 6f | 6e 2e 63 70 61 63 48 61 |.Solutio|n.cpacHa|
|00000840| 63 6b 20 43 6f 6e 74 65 | 73 74 31 2e 73 69 74 69 |ck Conte|st1.siti|
|00000850| 02 4a 50 61 72 74 53 49 | 54 21 00 00 00 00 00 00 |.JPartSI|T!......|
|00000860| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000870| 00 00 b1 b0 40 8e 00 00 | 00 00 00 00 01 9a 00 00 |....@...|........|
|00000880| 00 00 29 bc 7f 92 00 00 | 00 00 20 52 65 3a 20 46 |..).....|.. Re: F|
|00000890| 6f 6c 64 65 72 20 48 69 | 65 72 61 72 63 68 79 20 |older Hi|erarchy |
|000008a0| 44 75 70 6c 69 63 61 74 | 69 6f 6e 0d 00 00 00 00 |Duplicat|ion.....|
|000008b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000008c0| 00 00 00 00 00 00 00 00 | 00 04 36 35 37 a4 00 00 |........|..657...|
|000008d0| 00 00 00 00 00 00 00 00 | 00 01 be ab 00 00 05 f2 |........|........|
|000008e0| 00 00 02 90 02 07 31 32 | 2f 35 2f 39 38 34 30 30 |......12|/5/98400|
|000008f0| 30 32 31 3a 30 31 3a 35 | 36 20 31 39 39 38 00 00 |021:01:5|6 1998..|
|00000900| 00 00 00 48 00 0a 47 65 | 6e 65 76 61 00 00 00 00 |...H..Ge|neva....|
|00000910| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|00000920| 00 00 00 00 00 00 00 02 | 00 02 00 2c 00 08 02 1e |........|...,....|
|00000930| 02 18 00 2c 00 08 02 1e | 02 18 b1 ae ad 75 00 00 |...,....|.....u..|
|00000940| 07 3b 00 00 07 3b 00 00 | 02 df 01 00 00 00 00 04 |.;...;..|........|
|00000950| 00 01 00 01 00 00 01 00 | 00 00 01 54 00 00 00 54 |........|...T...T|
|00000960| 00 00 00 46 00 ce 0d f8 | 26 32 00 00 00 1c 00 46 |...F....|&2.....F|
|00000970| 00 01 4d 50 53 52 00 00 | 00 12 4d 57 42 42 00 00 |..MPSR..|..MWBB..|
|00000980| 00 1e 03 ed ff ff 00 00 | 00 00 00 00 00 00 03 f0 |........|........|
|00000990| ff ff 00 00 00 4c 00 00 | 00 00 00 00 00 00 00 00 |.....L..|........|
|000009a0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009b0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009c0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009d0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009e0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
|000009f0| 00 00 00 00 00 00 00 00 | 00 00 00 00 00 00 00 00 |........|........|
+--------+-------------------------+-------------------------+--------+--------+